package cn.zifangsky.disjoint;

/**
 * 不相交集
 *
 * @author zifangsky
 * @date 2019/1/16
 * @since 1.0.0
 */
public class DisjSets {
    /**
     * 根节点存储当前集合的高度，普通节点存储它的父节点
     */
    private int[] array;

    public DisjSets(int num) {
        this.array = new int[num];

        for(int i = 0; i < array.length; i++){
            array[i] = -1;
        }
    }

    /**
     * 对 element1 和 element2 执行 union 操作
     * <p>Note：</p>
     * <p>1、执行find操作时做了“路径压缩”优化</p>
     * <p>2、做union操作时根据“集合高度”进行合并</p>
     * @author zifangsky
     * @date 2019/1/16 16:14
     * @since 1.0.0
     */
    public void union(int element1, int element2){
        //element1的根节点
        int root1 = this.find(element1);
        int root2 = this.find(element2);
        //element1所在集合的高度
        int rootHeight1 = -array[root1];
        int rootHeight2 = -array[root2];

        //集合1比集合2高，则把element2挂载到集合1的根节点下面
        if(rootHeight1 > rootHeight2){
            array[element2] = root1;
        }else if(rootHeight1 < rootHeight2){
            array[element1] = root2;
        }
        //如果两个集合高度相等，如果是相同根节点，则不做处理，否则：
        else if(root1 != root2){
            //1. 集合1挂载到集合2下面
            array[root1] = root2;
            //2. 同时集合2的高度 + 1
            array[root2]--;
        }
    }

    /**
     * 对 element 执行 find 操作，返回 element 的根节点
     * @author zifangsky
     * @date 2019/1/16 16:14
     * @since 1.0.0
     */
    public int find(int element){
        //没有父节点
        if(array[element] < 0){
            return element;
        }else{
            //递归找到 element 的根节点，将 element 挂载到它的父节点，方便下次查找（路径压缩）
            array[element] = this.find(array[element]);
            return array[element];
        }
    }

    /**
     * 判断 element1 和 element2 是否相连
     * @author zifangsky
     * @date 2019/1/16 17:56
     * @since 1.0.0
     */
    public boolean isConnected(int element1, int element2){
        return this.find(element1) == this.find(element2);
    }

    /**
     * 获取现在有多少个不同的组
     * @author zifangsky
     * @date 2019/1/17 15:19
     * @since 1.0.0
     */
    public int getGroupNum(){
        int result = 0;

        for(int temp : array){
            //如果节点的值小于0，则表示当前是一个集合的根节点
            if(temp < 0){
                result++;
            }
        }

        return result;
    }
}
